【题解】 [国家集训队]Tree LCT luogu1501/bzoj2631 | Qiuly's blog!

【题解】 [国家集训队]Tree LCT luogu1501/bzoj2631

Posted on | Edited on | In | Comments:

Link-Cut-Tree 的懒标记下传正确食用方法。

1：+ u v c：将$u$到$v$的路径上的点的权值都加上自然数$c$;

  • 解决方法：

  • 很显然，我们可以$split(u,v)$来提取u,v这一段区间,提取完了将$Splay(v)$,然后直接在v上打加法标记$add$即可。

  • 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void pushadd(ll x,ll val){//打标记
	s[x]+=sz[x]*val,v[x]+=val,add[x]+=val;
	s[x]%=MOD,v[x]%=MOD,add[x]%=MOD;
}

inline void split(ll x,ll y){//LCT基本操作split,不再赘述
    makeroot(x);Access(y);Splay(y);
}

//(main函数中)：
if(op[0]=='+'){
	 scanf("%lld%lld%lld",&x,&y,&v);//输入信息
	 split(x,y);pushadd(y,v);//提取链条&打标记
}
2：- u1 v1 u2 v2：将树中原有的边$(u1,v1)$删除，加入一条新边$(u2,v2)$，保证操作完之后仍然是一棵树；
  • 解决方法：

  • 删除边即$cut$操作，加边即$link$操作。

  • 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline void link(ll x,ll y){
	makeroot(x);if(findroot(x)!=y)f[x]=y;
}
inline void cut(ll x,ll y){
	makeroot(x);split(x,y);
	if(findroot(y)==x&&f[x]==y&&!ch[x][1])
	   f[x]=ch[y][0]=0;return;
}//LCT基本操作link&cut，不再赘述

//(main函数中)：
if(op[0]=='-'){
     scanf("%lld%lld",&x,&y);cut(x,y);//删边
	 scanf("%lld%lld",&x,&y);link(x,y);//加边
}
3：* u v c：将$u$到$v$的路径上的点的权值都乘上自然数$c$；
  • 解决方法：

  • 很显然，我们可以$split(u,v)$来提取u,v这一段区间,提取完了将$Splay(v)$,然后直接在v上打乘法标记$mul$即可。(跟第一个操作基本同理)

  • 代码：

1
2
3
4
5
6
7
8
9
10
inline void pushmul(ll x,ll val){//打标记
	 s[x]*=val,v[x]*=val,mul[x]*=val,add[x]*=val;
	 s[x]%=MOD,v[x]%=MOD,mul[x]%=MOD,add[x]%=MOD;
}

//(main函数中)：
if(op[0]=='*'){
	 scanf("%lld%lld%lld",&x,&y,&v);
	 split(x,y);pushmul(y,v);
}
4：/ u v：询问$u$到$v$的路径上的点的权值和，求出答案对于51061的余数。
  • 解决方法：

  • $Splay(v)$时已经将所有节点更新过了(懒标记下传过了)，所以最后只需输出$s[v]$即可。

  • 代码：

1
2
3
4
5
//(main函数中)：
if(op[0]=='/'){
	 scanf("%lld%lld",&x,&y);
	 split(x,y);printf("%lld\n",s[y]);
}

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define RI register ll
#define A printf("A")
#define C printf(" ") 
#define MOD 51061
using namespace std;
const ll N=1e5+2;
template<typename _Tp> inline void IN(_Tp& dig){
    char c;bool flag=0;dig=0;
    while(c=getchar(),!isdigit(c))if(c=='-')flag=1;
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    if(flag)dig=-dig;
}ll f[N],s[N],v[N],sz[N],rev[N],mul[N],add[N],hep[N],ch[N][2];
inline ll get(ll x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
inline ll chk(ll x){return ch[f[x]][1]==x;}
inline void pushfilp(ll x){
	swap(ch[x][0],ch[x][1]);rev[x]^=1;
}
inline void pushup(ll x){
	s[x]=(s[ch[x][0]]+s[ch[x][1]]+v[x])%MOD;
	sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+1;
}
inline void pushmul(ll x,ll val){
	s[x]*=val,v[x]*=val,mul[x]*=val,add[x]*=val;
	s[x]%=MOD,v[x]%=MOD,mul[x]%=MOD,add[x]%=MOD;
}
inline void pushadd(ll x,ll val){
	s[x]+=sz[x]*val,v[x]+=val,add[x]+=val;
	s[x]%=MOD,v[x]%=MOD,add[x]%=MOD;
}
inline void pushdown(ll x){
	if(mul[x]!=1)pushmul(ch[x][0],mul[x]),pushmul(ch[x][1],mul[x]);
	if(add[x])pushadd(ch[x][0],add[x]),pushadd(ch[x][1],add[x]); 
	if(rev[x]){
		if(ch[x][0])pushfilp(ch[x][0]);
		if(ch[x][1])pushfilp(ch[x][1]);
	}rev[x]=0,add[x]=0,mul[x]=1;return;
}
inline void rotate(ll x){
	ll y=f[x],z=f[y],k=chk(x),v=ch[x][!k];
	if(get(y))ch[z][chk(y)]=x;ch[x][!k]=y,ch[y][k]=v;
	if(v)f[v]=y;f[y]=x,f[x]=z;pushup(y),pushup(x);
}
inline void Splay(ll x){
	ll y=x,top=0;hep[++top]=y;
	while(get(y))hep[++top]=y=f[y];
	while(top)pushdown(hep[top--]);
	while(get(x)){
		y=f[x],top=f[y];
		if(get(y))rotate((ch[y][0]==x)^(ch[top][0]==y)?y:x);
		rotate(x);
	}pushup(x);return;
}
inline void Access(ll x){
	for(register ll y=0;x;x=f[y=x])
	  Splay(x),ch[x][1]=y,pushup(x);
}
inline ll findroot(ll x){
	Access(x);Splay(x);
	while(ch[x][0])pushdown(x),x=ch[x][0];
	return x;
}
inline void makeroot(ll x){
    Access(x);Splay(x);pushfilp(x);
}
inline void split(ll x,ll y){
    makeroot(x);Access(y);Splay(y);
}
inline void link(ll x,ll y){
	makeroot(x);if(findroot(x)!=y)f[x]=y;
}
inline void cut(ll x,ll y){
	makeroot(x);split(x,y);
	if(findroot(y)==x&&f[x]==y&&!ch[x][1])
	   f[x]=ch[y][0]=0;return;
}char op[2];
int main(){
	ll n,m,x,y;scanf("%lld%lld",&n,&m);
	for(register int i=1;i<=n;++i)
	   mul[i]=sz[i]=v[i]=1;ll v;
	for(register int i=1;i<n;++i)
	   scanf("%lld%lld",&x,&y),link(x,y);
	for(register int i=1;i<=m;++i){
		scanf("%s",op);
		if(op[0]=='+'){
			scanf("%lld%lld%lld",&x,&y,&v);
			split(x,y);pushadd(y,v);
		}else if(op[0]=='-'){
			scanf("%lld%lld",&x,&y);cut(x,y);
			scanf("%lld%lld",&x,&y);link(x,y);
		}else if(op[0]=='*'){
			scanf("%lld%lld%lld",&x,&y,&v);
			split(x,y);pushmul(y,v);
		}else if(op[0]=='/'){
			scanf("%lld%lld",&x,&y);
			split(x,y);printf("%lld\n",s[y]);
		}
	}return 0;
}

因为$51061 * 51061$是会越过$int$界限的，所以我开的$longlong$(当然也可以开无符号$int$)
所以就没了。。。。。。

本文标题:【题解】 [国家集训队]Tree LCT luogu1501/bzoj2631

文章作者:Qiuly

发布时间:2019年02月17日 - 00:00

最后更新:2019年05月06日 - 14:04

原始链接:http://qiulyblog.github.io/2019/02/17/[题解]luoguP1501/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。